package leetcode;

import java.util.Arrays;

/**
 * description:给你一个区间数组 intervals ，其中intervals[i] = [starti, endi] ，且每个starti 都 不同 。
 * 区间 i 的 右侧区间 可以记作区间 j ，并满足 startj>= endi ，且 startj 最小化 。
 * 返回一个由每个区间 i 的 右侧区间 的最小起始位置组成的数组。如果某个区间 i 不存在对应的 右侧区间 ，则下标 i 处的值设为 -1 。
 *
 * author:zt
 * date:2022-05-20
 */
public class leetcode436 {
    public int[] findRightInterval(int[][] intervals) {
        int[] ans = new int[intervals.length];
        int[][] check = new int[intervals.length][2];
        for (int i = 0; i < intervals.length; i++) {
            check[i][0] = intervals[i][0]; check[i][1] = i;
        }
        Arrays.sort(check,(a,b)->a[0]-b[0]);

        for (int i = 0; i < intervals.length; i++) {
            int left = 0, right = check.length-1;
            while (left < right){
                int mid = (left + right) / 2;
                if (check[mid][0] < intervals[i][1]) left = mid + 1;
                else right = mid;
            }
            ans[i] = check[right][0] >= intervals[i][1] ? check[right][1]:-1;
        }


        return ans;
    }
}
